/* Copyright (c) 2009, Michael Patraw
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *     * Redistributions of source code must retain the above copyright
 *       notice, this list of conditions and the following disclaimer.
 *     * Redistributions in binary form must reproduce the above copyright
 *       notice, this list of conditions and the following disclaimer in the
 *       documentation and/or other materials provided with the distribution.
 *     * The name of Michael Patraw may not be used to endorse or promote
 *       products derived from this software without specific prior written
 *       permission.
 *
 * THIS SOFTWARE IS PROVIDED BY Michael Patraw ''AS IS'' AND ANY
 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED. IN NO EVENT SHALL Michael Patraw BE LIABLE FOR ANY
 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
#include <at/container/hash_map.h>

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/******************************************************************************\
\******************************************************************************/

/*
 * This is used for the string hashing function. Should be a prime.
 */
#define MULT 37



/*
 * A hash table entry.
 */
typedef struct entry_t *entryptr_t;
typedef struct entry_t {
    char *key;
    void *data;
    entryptr_t next;
} entry_t;



struct atHashMap_T {
    atuint N;
    atuint level;
    atuint malloc_size;
    atuint split;
    entryptr_t *entries;
};

/******************************************************************************\
\******************************************************************************/

/*
 * Returns the unbounded hash value of a string.
 */
static atuint hash(const char *str);



/*
 * Returns the size of a linear hash table based on initial size (N) and
 * the level (lvl).
 */
static atuint level_size(atuint N, atuint lvl);



/*
 * Returns the bounded hash value of a string.
 */
static atuint address(const char *key, atuint N, atuint lvl);



/*
 * Helper function for creating a hash table entry.
 */
static entryptr_t entry_malloc(const char *key, void *data);



/*
 * Helper function for freeing a hash table entry.
 */
static void entry_free(entryptr_t ptr);



/*
 * Increases the table size by one stage (doubles).
 */
static atint increase_hashmap_size(atHashMap_T h);



/*
 * Same as insert but doesn't rehash the entries at a split in the case
 * of a collision.
 */
static void insert_without_split(atHashMap_T h, entryptr_t entry);



/*
 * Rehashes all the entries at the split location. Calls increase_atHashMap_size
 * and insert_without_split in some cases.
 */
static atint rehash_split(atHashMap_T h);

#if 0 /* Not used */
static void atHashMap_print(atHashMap_T h);
static void atHashMap_stats(atHashMap_T h, atuint *size,
    atuint *taken, atuint *chain);
#endif



/*
 * The hash function.
 */
atHashMap_F hash_function = hash;

/******************************************************************************\
\******************************************************************************/

atHashMap_T atHashMap_Malloc(atuint n)
{
    atHashMap_T h;
    
    h = malloc(sizeof(*h));
    if (!h)
        return NULL;
    
   
    h->N = n;
    h->level = 0;
    h->malloc_size = level_size(h->N, h->level + 1);
    h->split = 0;
    h->entries = malloc(sizeof(entryptr_t) * h->malloc_size);
    
    if (!h->entries) {
        free(h);
        return NULL;
    }
    
    memset(h->entries, 0, sizeof(entryptr_t) * h->malloc_size);
    
    return h;
}



void atHashMap_Free(atHashMap_T h)
{
    atint i;
    entryptr_t ptr;

    for (i = 0; i < h->malloc_size; ++i) {
        if (h->entries[i]) {
            while (h->entries[i] != NULL) {
                ptr = h->entries[i];
                h->entries[i] = h->entries[i]->next;
                entry_free(ptr);
                /* Don't free the data pointer, it's the user's job. */
            }
        }
    }
    
    free(h->entries);
    free(h);
}



atint atHashMap_Insert(atHashMap_T h, const char *key, void *data)
{
    entryptr_t ptr;
    atuint a = address(key, h->N, h->level);
    
    if (a < h->split)
        a = address(key, h->N, h->level + 1);
    
    if (h->entries[a]) {
        for (ptr = h->entries[a]; ptr->next != NULL; ptr = ptr->next) {
            /* Check for duplicates, then replace. */
            if (strcmp(ptr->key, key) == 0) {
                ptr->data = data;
                return 0;
            }
        }
        /* Check again. */
        if (strcmp(ptr->key, key) == 0) {
            ptr->data = data;
            return 0;
        }
        
        ptr->next = entry_malloc(key, data);
        
        if (!ptr->next)
            return -1;
        
        /* Collision, so rehash the split. */
        if (rehash_split(h) == -1)
            return -1;
    }
    else {
        h->entries[a] = entry_malloc(key, data);
        
        if (!h->entries[a])
            return -1;
    }
    
    return 0;
}



void *atHashMap_Remove(atHashMap_T h, const char *key)
{
    entryptr_t ptr, prev = NULL;
    void *tmp;
    atuint a = address(key, h->N, h->level);
    
    if (a < h->split)
        a = address(key, h->N, h->level + 1);
    
    if (h->entries[a]) {
        for (ptr = h->entries[a]; ptr != NULL; ptr = ptr->next) {
            /* Check the list. */
            if (strcmp(ptr->key, key) == 0) {
                tmp = ptr->data;
                
                /* Restore the list. */
                if (prev)
                    prev->next = ptr->next;
                else
                    h->entries[a] = ptr->next;
                
                entry_free(ptr);
                
                return tmp;
            }
            
            prev = ptr;
        }
    }
    
    return NULL;
}



void *atHashMap_Retrieve(atHashMap_T h, const char *key)
{
    entryptr_t ptr;
    atuint a = address(key, h->N, h->level);
    
    if (a < h->split)
        a = address(key, h->N, h->level + 1);
    
    if (h->entries[a]) {
        for (ptr = h->entries[a]; ptr != NULL; ptr = ptr->next) {
            /* Check the list. */
            if (strcmp(ptr->key, key) == 0) {
                return ptr->data;
            }
        }
    }
    
    return NULL;
}



void atHashMap_Apply(atHashMap_T h, void (*fun) (const char *, void *))
{
    atint i;
    entryptr_t ptr;

    for (i = 0; i < h->malloc_size; ++i) {
        if (h->entries[i]) {
            ptr = h->entries[i];
            while (ptr != NULL) {
                fun(ptr->key, ptr->data);
            
                ptr = ptr->next;
            }
        }
    }
}



void atHashMap_SetHashFunc(atHashMap_F hf)
{
    hash_function = hf;
}

/******************************************************************************\
\******************************************************************************/

static atuint hash(const char *str)
{
    atuint key = 0;
    
    for ( ; *str; ++str)
        key = MULT * key + *str;
    
    return key;
}



static atuint level_size(atuint N, atuint lvl)
{
    return N * (atuint)pow(2, lvl);
}



static atuint address(const char *key, atuint N, atuint lvl)
{
    return hash_function(key) % level_size(N, lvl);
}



static entryptr_t entry_malloc(const char *key, void *data)
{
    entryptr_t ptr = malloc(sizeof(*ptr));
    
    if (!ptr)
        return NULL;
    
    ptr->key = malloc(sizeof(char) * (strlen(key) + 1));
    if (!ptr->key) {
        free(ptr);
        return NULL;
    }
    strcpy(ptr->key, key);
    
    ptr->data = data;
    ptr->next = NULL;
    
    return ptr;
}



static void entry_free(entryptr_t ptr)
{
    free(ptr->key);
    free(ptr);
}



static atint increase_hashmap_size(atHashMap_T h)
{
    atuint new_malloc_size;
    entryptr_t *tmp;

    h->level++;

    new_malloc_size = level_size(h->N, h->level + 1);

    tmp = realloc(h->entries, sizeof(entryptr_t) * new_malloc_size);
    if (!tmp)
        return -1;
    
    h->entries = tmp;

    memset(h->entries + h->malloc_size, 0,
        sizeof(entryptr_t) * (new_malloc_size - h->malloc_size));
    
    h->malloc_size = new_malloc_size;

    return 0;
}



static void insert_without_split(atHashMap_T h, entryptr_t entry)
{
    entryptr_t ptr;
    atuint a = address(entry->key, h->N, h->level + 1);
    
    if (h->entries[a]) {
        for (ptr = h->entries[a]; ptr->next != NULL; ptr = ptr->next) {
            /* Check for duplicates, then replace. */
            if (strcmp(ptr->key, entry->key) == 0) {
                ptr->data = entry->data;
                entry_free(entry);
                return;
            }
        }
        /* Check again. */
        if (strcmp(ptr->key, entry->key) == 0) {
            ptr->data = entry->data;
            entry_free(entry);
            return;
        }
        
        ptr->next = entry;
        
        /* Collision, but we don't rehash the split. */
    }
    else {
        h->entries[a] = entry;
    }
}



static atint rehash_split(atHashMap_T h)
{
    entryptr_t ptr, split_loc = h->entries[h->split];
    h->entries[h->split] = NULL;
    
    while (split_loc != NULL) {
        ptr = split_loc;
        split_loc = split_loc->next;
        
        /* We need to reset next back to NULL so entries aren't referring to
         * the wrong entry.
         */
        ptr->next = NULL;
        
        insert_without_split(h, ptr);
    }
    
    h->split++;
    if (h->split >= level_size(h->N, h->level)) {
        if (increase_hashmap_size(h) == -1)
            return -1; /* Lost memory at this point. */
        
        h->split = 0;
    }
    
    return 0;
}



#if 0 /* Not used */
static void atHashMap_print(atHashMap_T h)
{
    atint i;
    entryptr_t ptr;
    
    for (i = 0; i < h->malloc_size; ++i) {
        if (h->split == i)
                printf("--> ");
                
        if (h->entries[i]) {
            printf("Table[%d] = ", i);
            ptr = h->entries[i];
            while (ptr != NULL) {
                printf("%s -> ", ptr->key);
                
                ptr = ptr->next;
            }
            puts(" NULL");
        }
        else {
            printf("Table[%d] = NULL\n", i);
        }
    }
}



static void atHashMap_stats(atHashMap_T h, atuint *size,
    atuint *taken, atuint *chain)
{
    atint i;
    atint count;
    entryptr_t ptr;
    
    *chain = 0;
    *taken = 0;
    *size = h->malloc_size;
    
    for (i = 0; i < h->malloc_size; ++i) {   
        if (h->entries[i]) {
            (*taken)++;
        
            ptr = h->entries[i];
            count = 0;
            while (ptr != NULL) {
                count++;
                ptr = ptr->next;
            }
            
            if (count > *chain)
                *chain = count;
        }
    }
}
#endif
